﻿/*
题目: 24 点游戏

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法，而不是整数除法。
例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。
如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

https://leetcode.cn/problems/24-game/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    /**
    * 1. double 之间的比较不能用 ==, 使用差值，判断是否小于 10^-6
    * 2. nums[i] op nums[j] 之后，一定存在 nums[j] op nums[i]
    * 3. 四个数，抽两个数出来计算，组成 3 个数，重复这个过程，变成 2 个数 ...
    */

#define TARGET 24
#define DEVIATION (1e-6)    // 10 的 -6 次方

    // 长度为 4，回溯
    bool judgePoint24(vector<int>& cards) {
        vector<double> nums{ cards.begin(), cards.end() };
        return backtrace(nums);
    }

    bool backtrace(vector<double>& nums) {
        if (nums.size() == 1) {
            if (fabs(nums[0] - TARGET) <= DEVIATION)  return true;
            return false;
        }

        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                vector<double> possible = get_possible(nums[i], nums[j]);
                // 再和剩下的元素合起来
                vector<double> remain;
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j)     remain.push_back(nums[k]);
                }

                for (double elem : possible) {
                    remain.push_back(elem);
                    if (backtrace(remain) == true)    return true;
                    remain.pop_back();
                }
            }
        }

        return false;
    }

    // 获得两个数所有的计算结果
    vector<double> get_possible(double a, double b) {
        vector<double> possible;

        possible.push_back(a + b);
        possible.push_back(b - a);
        possible.push_back(a - b);
        possible.push_back(a * b);

        if (a != 0)
            possible.push_back(b / a);
        if (b != 0)
            possible.push_back(a / b);

        return possible;
    }
};
